\section{Eliptické krivky}

Tento často počuteľný výraz znie veľmi matematicky. Napriek tomu si
ukážeme, že je to pomerne jednoduchý spôsob, ako generovať istý týp
grúp, v ktorých budeme vedieť následne počítať známe kryptografické
konštrukcie.

\begin{poznamka}
    Osobný názor doc. Staneka je, že eliptické krivky nahradia do
    niekoľko rokov RSA. Napríklad odporúčania na šifrovanie vládnych
    dokumentov v USA sa už ani nezmieňujú o používaní RSA. Nevýhodou
    RSA je totiž veľmi dlhý modulus pri ekvivalentnej bezpečnosti.
    Môžeme teda povedať, že diskrétny logaritmus začne vládnuť svetu
    :-)
\end{poznamka}

Ešte predtým, ako si povieme, čo to vlastne tieto krivky sú, uvedieme
si najväčšiu výhodu -- pre sofistikované algoritmy na
výpočet diskrétneho algoritmu ako napríklad general number field
sieve, index calculus nepoznáme v súčasnosti úpravy, ktoré by umožnili
ich aplikáciu na eliptické krivky. Dajú sa teda použiť iba generické
algoritmy. Tým pádom môžeme používať menšie kľúče, budeme mať menšie
podpisy, ... Hneď ale pripojíme aj varovanie -- existujú špecifické
útoky na isté typy eliptických kriviek, preto je potrebné venovať
generovaniu krivky dostatočnú pozornosť.

\begin{definicia}[Eliptická krivka]
    Pod eliptickou krivkou nad poľom $F$ budeme označovať množinu
    všetkých takých bodov $(x,y)$, ktoré vyhovujú rovnici
    \begin{equation*}
        x^3 + A x + B = y^2
    \end{equation*}
    kde $A,B$ sú vopred zvolené konštanty.
    Pre body $(x,y)$ si zavedieme grupovú operáciu sčítania ``+''
    a taktiež pridáme neutrálny prvok $\mathbf{0}$
    ktorý bude predstavovať bod v nekonečne.
\end{definicia}

Ak si zoberieme pole $F=R$, eliptická krivka $x^3 -3x+3=y^2$ je
zobrazená na obrázku \ref{fig:elliptic1}

\begin{figure}[h]
    \centering
    \includegraphics{img/09/elliptic.1.mps}
    \caption{Eliptická krivka $x^3 - 3x +3 = y^2$ v reálnych číslach}
    \label{fig:elliptic1}
\end{figure}

Ešte predtým, ako si ukážeme sčítanie bodov, ktoré nie je úplne
triviálne, budeme sa zaoberať podmienkou na to, aby daná krivka bola
regulárna.

Predstavme si, že krivka je singulárna, t.j. existuje dvojitý koreň,
označme ho $a$ a označme tretí koreň $b$ (neplatí nutne $a\ne b$).
Dostávame
\begin{align*}
    (x-a)^2 (x-b) &= x^3 + Ax + B \\
    x^3 + x^2 (-b -2a) + x (2ab + a^2) + (-b a^2) &= x^3 + Ax + B
\end{align*}
Z koeficientu pred $x^2$ dostávame $b=-2a$ a teda
\begin{align*}
    A &= 2ab + a^2 = -3 a^2 \\
    B &= -b a^2 = 2 a^3
\end{align*}
Čo nastáva v prípade, ak
\begin{equation*}
    4 A^3 + 27 B^2 = 0
\end{equation*}
Pri generovaní kriviek budeme teda musieť otestovať túto rovnicu a v
prípade rovnosti generovať novú krivku.

Poďme ale späť k sčítavaniu
\begin{definicia}[Sčítanie bodov eliptickej krivky]
    Majme body $P=[x_1,y_1]$ a $Q=[x_2,y_2]$.\footnote{Body
        eliptických kriviek zvykneme označovať veľkými písmenami}
    Nech $P \ne -Q$, kde unárnou operáciou ``$-$'' nad bodom
    $(x,y)$ budeme označovať bod $(x,-y)$.
    Potom operáciu sčítania $P+Q$ definujeme nasledovne:

    \begin{equation*}
        P+Q = [ \underbrace{\lambda^2 - x_1 - x_2}_{x_3}, \ 
            \lambda (x_1 - x_3) - y_1]
    \end{equation*}
    kde $\lambda$ je definované ako
    \begin{equation*}
        \lambda =
            \begin{cases}
                (y_2 -y_1)(x_2 - x_1)^{-1} \quad & P \ne Q \\
                (3 x_1^2 + A)(2 y_1)^{-1} \quad & P = Q
            \end{cases}
    \end{equation*}
    Sčítanie pre prípad $P = -Q$ definujeme ako $P+Q=\mathbf{0}$.
\end{definicia}

Budeme tvrdiť, že množina bodov $\{(x,y)\} \union \mathbf{0}$
eliptickej krivky spolu s operáciu ``$+$'' bude tvoriť grupu. Toto
netriviálne algebraické tvrdenie prenecháme na neveriaceho
čitateľa. Ak teda zoberieme ako $F$ nejaké konečné
pole, dostávame konečnú grupu.

Predchádzajúca definícia sčítania možno nebola veľmi intuitívna.
Ukážeme si teda iný prístup k definícii sčítania bodov na eliptickej
krivke. Spôsob je to čisto grafický.
Ak máme body $P,Q$, body $-P, 2P, P+Q$ získame postupne ako
zrkadlenie bodu $P$ podľa osi $x$,
zkradlenie priesečníka dotyčnice v bode $P$ s krivkou
a zkradlenie tretieho priesečníka priamky prechádzajúcej bodmi $P,Q$ a
eliptickej krivky. Názorne to možno vidieť na obrázku
$\ref{fig:elliptic-plus}$.

\begin{figure}
    \centering
    \subfigure[$-P$]{
        \includegraphics{img/09/elliptic.2.mps}
    }
    \subfigure[$2P$]{
        \includegraphics{img/09/elliptic.3.mps}
    }
    \subfigure[$P+Q$]{
        \includegraphics{img/09/elliptic.4.mps}
    }

    \caption{Grafické sčítanie na eliptických krivkách}
    \label{fig:elliptic-plus}
\end{figure}

\begin{priklad}
    Uvedieme si ilustratívny príklad eliptickej krivky. Uvažujme
    rovnicu
    \begin{equation*}
        y^2 = x^3 + x + 1 \pmod{11}
    \end{equation*}
    Vypočítajme body vyhovujúce krivke:

    \begin{table}[h!]
        \centering
        \begin{tabular}{c|c|c}
            $x$ & $x^3 + x + 1 \pmod{11}$ & $y$ \\
            \hline 0 & 1 & 1, 10 \\
            \hline 1 & 3 & 5, 6 \\
            \hline 2 & 0 & 0 \\
            \hline 3 & 9 & 3, 8 \\
            \hline 4 & 3 & 5, 6 \\
            \hline 5 & 4 & 2, 9 \\
            \hline 6 & 3 & 5, 6 \\
            \hline 7 & 10 & - \\
            \hline 8 & 4 & 2, 9 \\
            \hline 9 & 2 & - \\
            \hline 10 & 10 & - \\
        \end{tabular}
        \caption{Body ležiace na eliptickej krivke $x^3 + x + 1
        \pmod{11}$}
    \end{table}
    Dostávame teda, že množina bodov našej krivky je
    \begin{equation*}
       E=\Big\{ [0,1], [0,10], [1,5], [1,6],
                [2,0], [3,3], [3,8],
                [4,5], [4,6], [5,2], [5,9],
                [6,5], [6,6], [8,2], [8,9], \mathbf{0} \Big\}
    \end{equation*}
    Príklad niektorých sčítaní:
    \begin{align*}
        [2,0] + [2,0] &= 0 \\
        [1,5] + [1,6] &= 0 \\
        [0,1] + [3,3] &= [6, 6] 
    \end{align*}
\end{priklad}

Dostali sme sa do stavu, že máme grupu bodov eliptickej krivky. Toto
samo o sebe je síce pekné, ale na naše účely to nestačí. To, čo by sme
momentálne potrebovali vedieť je, že aká veľká daná grupa je (koľko má
prvkov) a či obsahuje malé podgrupy.

Druhá vlastnosť nás nezaujíma len tak zo zvedavosti -- Pohlig Hellmanov
algoritmus, ktorý dobre poznáme by v tomto prípade narobil paseku a
bezpečnosť schémy by bola ohrozená. Preto by sme boli najradšej, ak by
sme mali prvočíselnú grupu. Začneme však postupne:

\begin{veta}[Hasseho veta]
    Nech $E$ je grupa bodov eliptickej krivky $\pmod{p}$.
    Potom platí
    \begin{equation*}
        p + 1 - 2 \sqrt{p} \le |E| \le p + 1 + 2 \sqrt{p}
    \end{equation*}
\end{veta}

Dá sa teda garantovať, že počet bodov eliptickej krivky je dostatočne
veľký, no o veľkých prvočíselných faktoroch nám to nič nepovie.
Na pomoc príde Schoofov algoritmus, ktorý v čase
$O((\log{p})^6)$ vie presne určiť počet bodov krivky. Problém je však
v tom, že na praktické účely je aj toto priveľa -- v roku 2001 vraj
výpočet pre 200 bitové čísla trval niekoľho hodín. Teda, v súčasnosti
nie je efektívne počítať veľkosť grupy tvorenej bodmi eliptickej
krivky, minimálne nie na takej úrovni ako sa používa RSA napríklad pri
zabezpečovaní secure http.

Ako teda, že sa eliptické krivky používajú v praxi? Odpoveď je
jednoduchá -- niekto si dal záležať a našiel takú grupu, že $|E|$ je
prvočíslo. Napríklad, v štandarde DSS (Digital Signature standard), v
časti o ECDSA (Elliptic Curve DSA) sa explicitne uvádzajú krivky,
ktoré sa majú používať. Tieto krivky majú napevno zvolené $A=-3$ a $B$
bolo volené tak, aby $|E|$ bolo prvočíslo -- napríklad tak, že sa
postupne preberali možné parametre $B$ a $p$.

\begin{poznamka}[Pre fanúšikov algebry]
    Dá sa ukázať, že grupa $(E,+)$ je izomorfná so
    $Z_{n_1} \times Z_{n_2}$, kde $n_2$ delí $n_1$, $n_2$ delí $p-1$ a
    $n_1,n_2$ sú jednoznačne určené.
    Navyše, vhodnou voľbou parametrov sa dá dosiahnuť, že
    $n_2=1$, t.j. dostávame izomorfizmus so $Z_p^*$. Prirodzenou
    otázkou v takomto prípade je, či izomorfizmus nezmenšuje
    bezpečnosť -- mohli by sa dať aplikovať klasické algoritmy na
    faktorizáciu aj na eliptické krivky.
    Odpoveď je, že bezpečnosť krivky (grupy) nám tento izomorfizmus
    nepokazí. Také chabé zdôvodnenie je, že síce vieme o tom, že tam
    izomorfizmus je, na druhej strane je dostatočne komplikovaný.
\end{poznamka}

Teraz si predstavíme algoritmus ECDSA určený na digitálne podpisovanie
správ.
Začneme parametrami, ktoré sa zvyknú uvádzať v tabuľkách eliptických
kriviek:
\begin{itemize}
    \item $A$
    \item $B$
    \item $p$ -- prvočíselný modulus
    \item $FR$ -- field representation -- buď ako polynómy nad
        $GF(2^m)$ (binárne polia)
        alebo ako mocniny generátora (prvočíselné polia)
        alebo Koblitzove krivky.
    \item $seed$ -- keď niekto neverí vygenerovaným krivkám, môže si
        overiť, že boli vygenerované podľa tohoto seedu.
    \item $G$ -- generátor prvočíselnej podgrupy, je to bod patriaci krivke
    \item $n$ -- rád $G$ (generátora podgrupy), je to prvočíslo
    \item $k$ -- kofaktor, $k=|E| / n$
\end{itemize}
\begin{poznamka}
    V štandarde sa používajú krivky s kofaktorom $k=1,2,4$, teda (ako
    sa ukáže), dĺžka verejného a privátneho kľúča je približne
    rovnaká.
\end{poznamka}

Čo sa týka prvočíselného modula $p$, štandard prechádza plejádou
hodnôt od 192 po 521 bitov.
Príklady:
\begin{itemize}
    \item $p=2^{192} - 2^{64} - 1$ 
    \item $p=2^{521} - 1$.
\end{itemize}
Vo všeobecnosti sa volia takmer mersenovské prvočísla.

\begin{poznamka}
    Pre záujemcov máme výpis jednej takej krivky zo štandardu FIPS 186-3
    (\cite{fips186}).Krivka je v štandarde označená
    ``D.1.3.3.2 Curve B-283''.
    \begin{itemize}
        \item
            \begin{verbatim}
n =   77706 7556890291 6283677847 6272940756 2656962592 
            4376904889 1091965267 7004427778 7378692871;
            \end{verbatim}
        \item Polynomial Basis:  
            \begin{verbatim}
B   = 27b680a c8b8596d a5a4af8a 19a0303f ca97fd76
              45309fa2 a581485a f6263e31 3b79a2f5;
G_x = 5f93925 8db7dd90 e1934f8c 70b0dfec 2eed25b8
              557eac9c 80e2e198 f8cdbecd 86b12053; 
G_y = 3676854 fe24141c b98fe6d4 b20d02b4 516ff702
              350eddb0 826779c8 13f0df45 be8112f4; 
            \end{verbatim}
        \item Normal Basis:  
            \begin{verbatim}
seed = 77e2b073 70eb0f83 2a6dd5b6 2dfc88cd 06bb84be;
B    =  157261b 894739fb 5a13503f 55f0b3f1 0c560116
                66331022 01138cc1 80c0206b dafbc951;
G_x  =  749468e 464ee468 634b21f7 f61cb700 701817e6
                bc36a236 4cb8906e 940948ea a463c35d; 
G_y  =  62968bd 3b489ac5 c9b859da 68475c31 5bafcdc4
                ccd0dc90 5b70f624 46f49c05 2f49c08c; 
            \end{verbatim}
    \end{itemize}
\end{poznamka}

Ale vráťme sa k samotnému podpisovaniu. Prvou častou je generovanie
kľúčov popísané v \ref{proc:genecdsa}.

\begin{procedure}[H]
    \caption{GenECDSA($n$)}
    \label{proc:genecdsa}
    $sk = d \inr \{1, \dots, n-1\}$ \;
    $pk = Q = d*G = \underbrace{G+G+G+\dots+G}_{d \times}$ \;
\end{procedure}

Podpisovanie budeme robiť veľmi podobne podpisovaniu v klasickej DSA
schéme, teda, podpisom bude správa $\langle r,s \rangle$ získaná 
volaním funkcie \ref{proc:signecdsa}.

\begin{procedure}[H]
    \caption{SignECDSA($m,sk=d, D=\langle q,FR, A,B,G,n,h \rangle$)}
    \label{proc:signecdsa}
    \Repeat{$s =0$}{
        \Repeat{$r =0$}{
            $k \inr \{ 1, \dots, n-1 \}$ \;
            $\langle x_1, y_1 \rangle = k * G$ \;
            $r \assign x_1 \pmod{n}$ \;
        }
        $s \assign k^{-1}(\mbox{SHA-1}(m) + d\cdot r) \pmod{n}$ \;
    }
    \Return{$\langle r,s \rangle$}\;
\end{procedure}

Čitateľ sa možno čuduje, prečo pri podpisovaní vôbec nevyužívame
súradnicu $y_1$ z bodu $k*G$ eliptickej krivky. Jeden z dôvodov môže
byť nasledujúci -- $y_1$ môže nadobúdať len 2 rôzne hodnoty. Preto
je zrejme výhodné obetovať stratu bezpečnosti o 1 bit výmenov za veľkosť
podpisu (ak by sme chceli podpisovať aj $y_1$, potrebovali by sme
zväčšiť veľkosť podpisu). Dĺžka podpisu ECDSA je $2 \lceil \log n \rceil$.

Overovanie podpisu je taktiež nápadne podobné štandardnému DSA
algoritmu a je popísané vo funkcii \ref{proc:verifyecdsa}.

\begin{procedure}[H]
    \caption{verifyECDSA($m,sig=\langle r,s \rangle,pk= Q,
            D=\langle q,FR, A,B,G,n,h \rangle$)}
    \label{proc:verifyecdsa}
    \lIf{$(r \not \in \{1, \dots, n-1\} \lor
           s \not \in \{1, \dots, n-1\})$}{reject}\;
    $u_1 \assign \mbox{SHA-1}(m) \cdot s^{-1} \pmod{n}$ \;
    $u_2 \assign r \cdot s^{-1} \pmod{n}$ \;
    $X \assign u_1 * G + u_2 * Q$ \;
    \lIf{$(X=\mathbf{0})$}{reject\;}
    $ \langle x_1, y_1 \rangle \assign X$ \;
    \eIf{$x_1 \pmod{n} = r$}{
        accept\;
        }{
        reject\;
        }
\end{procedure}

Ako vždy by bolo pekné ukázať, že overovanie korektných podpisov
je korektné.
Predpokladajme, že správa bola podpísaná správne, teda platí
$s = k^{-1} (\mbox{SHA-1}(m) + d r) \pmod{n}$.
Potom 
\begin{equation*}
    k \equiv s^{-1} (\mbox{SHA-1}(m) + d r)  \equiv
    s^{-1} \mbox{SHA-1}(m) + s^{-1} d r \equiv u_1 + u_2 d \pmod{n}
\end{equation*}
Tým pádom $u_1 G + u_2 Q = (u_1 + u_2 d)*G = k*G$.
To, že je ťažké sfalšovať podpis sa dokáže podobne ako v krypto I pre
DSA. Z podobných implementačných detailov tiež môžeme vypichnúť
nutnosť testovania,
že $r,s$ patria do správneho intervalu, inak hrozí pomerne jednoduchá
možnosť falšovania podpisov.

V prípade, že čitateľa zaujalo podpisovanie správ pomocou DSA na eliptických
krivkách, vrelo mu odporúčame pozrieť sa na \cite{ecdsa}.

\begin{poznamka}
    Uvažujme ElGamalov šifrovací algoritmus. Ak si dobre spomenieme,
    tento algoritmus pracuje v ľubovoľnej cyklickej grupe
    prvočíselného rádu. Preto sa dá realizovať aj na eliptických
    krivkách. Má to ale drobný háčik.
    Ako si čitateľ iste všimol, pri podpisovaní nepotrebujeme
    žiadnym spôsobom vedieť prevádzať správu resp. jej hash na body
    eliptickej krivky, všetky výpočty (až na násobenie bodu krivky
    číslom) sa dejú v $Z_n$. Pri šifrovaní ElGamalom 
    je ale situácia odlišná -- potrebujeme vedieť efektívne prevádzať
    medzi bodmi krivky a bitovými reťazcami. Existujú algoritmy, ktoré
    toto vedia istým spôsobom zabezpečiť (tieto algoritmy ale väčšinou
    používajú rôzne prvočíselné podgrupy eliptickej krivky, nie
    pôvodne vygenerovanú).
\end{poznamka}

Pretože problém mapovania správy na body eliptickej krivky je pomerne
náročný, v praxi sa na šifrovanie používa nasledujúca modifikácia
ElGamalovho šifrovacieho systému. Na šifrovanie budeme používať
kľúče vygenerované tým istým spôsobom ako pri podpisovaní, máme teda
$sk=d \inr \{1,\dots,n-1\}$ a $pk=Q=d*G$.

\begin{procedure}[H]
    \caption{ECEG::encrypt($m$)}
    \Repeat{$(x_0  =0)$}{
        $k \inr \{ 1, \dots, n-1\}$ \;
        $ R \assign k*G$ \;
        $ \langle x_0, y_0 \rangle \assign k*Q$ \;
    }
    $ s \assign x_0 * m \pmod{p}$ \;
    \Return $\langle R, s \rangle$ \;
\end{procedure}

\begin{procedure}[H]
    \caption{ECEG::decrypt($\langle R, s\rangle$)}
    \tcp{platí $d*R = d k * G = kd*G = k*Q$}
    $\langle x_0, y_0 \rangle \assign d*R$ \;
    $ m \assign  s * x_0^{-1} \pmod{p}$ \;
    \Return $m$ \;
\end{procedure}

\begin{poznamka}
    Výpočet súkromného kľúča je ekvivalentný problému diskrétneho
    logaritmu v danej grupe.
\end{poznamka}
\begin{poznamka}
    Pretože útočník má k dispozícii $d*G, k*G$ a chce $dk*G$, je
    zlomenie schémy ekvivalentné riešeniu Diffie-Hellmanovho problému.
\end{poznamka}
\begin{poznamka}
    Opäť používame iba jednu súradnicu, pretože druhú si útočník vie
    ľahko dopočítať. Preto je tiež možné hodnotu
    $R = \langle x', y' \rangle$ v šifrovom texte nahradiť dvojicou
    $\langle x', + \rangle$ resp. $\langle x', - \rangle$
    a ušetríme na veľkosti šifrového textu.
\end{poznamka}

Teraz trochu pouvažujeme nad tým, ako čo najviac zefektívniť prácu na
eliptických krivkách. Uvažujme napríklad výpočet $15*G$ štandardnou
exponenciáciou (v našom prípade ale neumocňujeme, iba násobíme):
$15*G = 8*G + 4*G + 2*G + G$. Tento zápis vieme ale spraviť aj
efektívnejšie : $15*G = 16*G - G$. V prvom rade si môžeme všimnúť, že
sme pridali jedno sčítanie $16*G = 8*G + 8*G$, ušetrili sme ale dve
sčítania. Na druhej strane, výpočet inverzného prvku je úplne zadarmo,
keďže je to iba zmena znamienka $y$-ovej súradnice.

Vo všeobecnosti, čím viac núl má číslo, ktorým chceme
násobiť, tým menej operácii budeme potrebovať. V binárnej sústave s
tým veľmi veľa nenarobíme, lebo existuje iba jedna reprezentácia
čísla. Môžeme sa však inšpirovať príkladom, kde sme použíli cifru
``$-1$'' a skúsiť použiť číselnú sústavu s ciframi $0,1,-1$.

\begin{definicia}[NAF -- Non Adjacent Form]
    Uvažujme reprezentáciu čísla v $\{0,1,-1\}$-kovej sústave.
    Túto reprezentáciu budeme nazývať Non Adjacent Form, ak každé dve
    nenulové cifry budú oddelené aspoň jednou nulovou.
\end{definicia}

\begin{priklad}
    Uvažujme nasledujúce zápisy čísla 7:
    \begin{align*}
        (0\ 1\ 1\ 1)_2 &= 4+2+1=7 \\
        (1\ 0\ {-1}\ 1)_2 &= 8-2+1=7 \\
        (1\ {-1}\ 1\ 1)_2 &= 8-4+2+1=7 \\
        (1\ 0\ 0\ {-1})_2 &= 8-1=7
    \end{align*}
    Z týchto zápisov je NAF iba posledný.
\end{priklad}

\begin{poznamka}
    NAF reprezentácia pre dané celé číslo je jedinečná, teda
    neexistujú 2 rôzne NAF reprezentácie toho istého čísla.
\end{poznamka}

To čo je ale pre nás zaujímavé je nasledovná vec -- uvažujme náhodné
binárne číslo. Očakávaný počet jednotkových bitov je práve polovica.
Naproti tomu, v NAF je očakávaný počet nenulových bitov iba jedna
tretina. Preto sa oplatí najskôr číslo previesť do NAF reprezentácie a
až potom počítať násobenie v grupe. Algoritmus na takýto prevod je
napríklad \ref{algo:naf}.

\begin{algorithm}[H]
    \caption{Algoritmus na prevod z binárnej reprezetácie do NAF}
    \label{algo:naf}
    $i \assign 0$\;
    \While{$i < bitlength$}{
        \If{$(bit[i] = 0)$}{
            $i \assign i+1$ \;
            continue \;
        }
        \If{$(bit[i]=1) \land (bit[i+1]=0)$}{
            $i \assign i+2$ \;
            continue \;
        }
        \tcp{našli sme po sebe idúce jednotky, zistíme pokiaľ siahajú}
        $j \assign i$\;
        \lWhile{$(bit[j]=1)$}{$j \assign j+1$\;}
        \tcp{a nahradíme postupnosťou 1 0 ... 0 -1}
        $bit[j] \assign 1$ \;
        $bit[i+1],\dots,bit[j-1] \assign 0$ \;
        $bit[i] \assign -1$ \;
        \BlankLine
        $i \assign j$ \;
    }
\end{algorithm}

Základná myšlienka je nahradiť dlhé bloky po sebe idúcich jednotiek za
1 0 0 ... 0 -1.

\begin{priklad}
    Ukážka behu algoritmu: \\
    \begin{center}
        \begin{tabular}{rrrrr}
            0 1 1 1& 0 1 1 1& 0 1 0 1& 0 0 0 1& 1 1 1 1 \\
            0 1 1 1& 0 1 1 1& 0 1 0 1& 0 0 \emph{1 0}& \emph{0 0 0-1} \\
            0 1 1 1& \emph{1 0 0-1}& 0 1 0 1& 0 0 1 0& 0 0 0-1 \\
            \emph{1 0 0 0}&\emph{-1} 0 0-1& 0 1 0 1& 0 0 1 0& 0 0 0-1
        \end{tabular}
    \end{center}
    Z 13-tich jednotiek sme dostali 7 nenulových prvkov.
\end{priklad}
